# 反转一个单链表。

# 示例:

# 输入: 1->2->3->4->5->NULL
# 输出: 5->4->3->2->1->NULL
# 进阶:
# 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    """
    5.next = 4
    4.next = 3
    """

    def reverseList_my(self, head: ListNode) -> ListNode:
        """自己想的方法
        """
        if head is None or head.next is None:
            return head
        l = []
        while head:
            l.append(head)
            head = head.next
        
        length = len(l) # 5
        tmp = l[length-1]
        new_head = tmp
        for index in range(len(l)-1):
            node = l[length - index - 1]
            node.next = l[length - index - 2]
        else:
            l[length - index -2].next = None

        return new_head


    def reverseList(self, head: ListNode) -> ListNode:
        """别人的三指针　https://www.jianshu.com/p/f7534f8d7bf2
        迭代法:
        从前往后遍历链表，定义三个指针分别指向相邻的三个结点，
        反转前两个结点，即让第二个结点指向第一个结点。然后依次往后移动指针，
        直到第二个结点为空结束，再处理链表头尾即可。
        """
        if head is None or head.next is None:
            return head
        # 至少有2个
        p1 = head
        p2 = head.next
        p3 = p2.next

        while p2:
            # 在循环中调换p1,p2
            p3 = p2.next
            p2.next = p1
            p1 = p2
            p2 = p3
        
        head.next = None
        head = p1
        return head


    def reverse(self, node):
        if not node.next:
            return node
        else:
            node.next = self.reverse(node.next)

        return node

if __name__ == "__main__":
    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(3)
    d = ListNode(4)
    e = ListNode(5)
    a.next = b
    b.next = c
    c.next = d
    d.next = e
    from list_node import print_list
    s = Solution().reverseList(a)
    print_list(s)


